#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int hanota(vector<int>& A, vector<int>& B, vector<int>& C)
    {
        int sum = 0;
        sum  = dfs(A, B, C, A.size());
        return sum;
    }

    int dfs(vector<int>& A, vector<int>& B, vector<int>& C, int num)
    {
        if (num == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return 1;
        }
        int sum1 = dfs(A, C, B, num - 1);
        C.push_back(A.back());
        A.pop_back();
        int sum2 = dfs(B, A, C, num - 1);
        return sum1 + sum2 + 1;

       /* if (num == 1)
        {
            return 1;
        }
        return dfs(A, C, B, num - 1) + 1 + dfs(B, A, C, num - 1);*/
    }
};

int main()
{
    vector<int> A{ 1,2,4,11,3,4,2,1,4 };
    vector<int> B;
    vector<int> C;
    Solution s1;
    cout << s1.hanota(A, B, C) << endl;
    for (auto c : C)
    {
        cout << c << " ";
    }
    cout << endl;

	return 0;
}